package 剑指offer;

/**
 * @author: tyy 剑指 Offer
 * 367. 有效的完全平方数
    给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
    进阶：不要 使用任何内置的库函数，如  sqrt 。
 * @create: 2021-10-31 17:40
 * @description:
 **/
// 利用 1+3+5+7+9+…+(2n-1)=n^2，即完全平方数肯定是前n个连续奇数的和
public class Solution17 {
    /**二分法
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;

        while(left <= right) {
            int mid = left + (right - left)/2;
            // 或者 int mid = (right + left)/2;
            long k = (long)mid*mid;
            if(k == num) {
                return true;
            }
            if(k < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
    public boolean isPerfectSquare2(int num) {
        double sqrt = Math.sqrt(num);
        String s = String.valueOf(sqrt);
        return s.substring(s.length()-1).equals("0");
    }
    public boolean isPerfectSquare1(int num) {
        if (num == 1) {
            return true;
        }
        int n = num / 2;
        boolean flag = false;
        for (int i = 1; i <= n; i++) {
            int i2 = i * i;
            if (i2 == num) {
                flag = true;
                break;
            }
            if (i2 > num) {
                flag = false;
                break;
            }
        }
        return flag;
    }
    public static void main(String[] args) {
        int num = 15;
        boolean perfectSquare = new Solution17().isPerfectSquare(num);
        System.out.println("perfectSquare = " + perfectSquare);
                

    }
}